"""
栈 (Stack) - Python实现
后进先出(LIFO)，所有操作O(1)
"""

class Stack:
    """使用list实现栈"""
    def __init__(self):
        self._items = []
    
    def push(self, item):
        """压栈"""
        self._items.append(item)
    
    def pop(self):
        """弹栈"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self._items.pop()
    
    def peek(self):
        """查看栈顶"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self._items[-1]
    
    def is_empty(self):
        return len(self._items) == 0
    
    def size(self):
        return len(self._items)
    
    def __str__(self):
        return f"栈底 → {self._items} ← 栈顶"

# 应用场景1: 括号匹配
def check_brackets(expression):
    """检查括号是否匹配"""
    stack = Stack()
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in expression:
        if char in pairs:
            stack.push(char)
        elif char in pairs.values():
            if stack.is_empty() or pairs[stack.pop()] != char:
                return False
    
    return stack.is_empty()

# 应用场景2: 表达式求值
def evaluate_postfix(expression):
    """计算后缀表达式"""
    stack = Stack()
    
    for token in expression.split():
        if token.isdigit():
            stack.push(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+': stack.push(a + b)
            elif token == '-': stack.push(a - b)
            elif token == '*': stack.push(a * b)
            elif token == '/': stack.push(a // b)
    
    return stack.pop()

def main():
    print("╔════════════════════════════════════════╗")
    print("║   栈 (Stack) - Python实现               ║")
    print("╚════════════════════════════════════════╝")
    
    stack = Stack()
    stack.push(10)
    stack.push(20)
    stack.push(30)
    print(f"\n{stack}")
    print(f"弹出: {stack.pop()}")
    print(f"栈顶: {stack.peek()}")
    
    print("\n--- 括号匹配 ---")
    test_cases = ["{[()]}", "{[(])}"]
    for expr in test_cases:
        result = "匹配✓" if check_brackets(expr) else "不匹配✗"
        print(f"  {expr} → {result}")
    
    print("\n--- 表达式求值 ---")
    postfix = "5 3 + 2 *"
    print(f"  {postfix} = {evaluate_postfix(postfix)}")
    
    print("\n✅ 优势: 所有操作O(1)，LIFO适合很多场景")
    print("⚠️ 局限: 只能访问栈顶")
    print("💡 应用: 括号匹配、函数调用、浏览器后退")

if __name__ == "__main__":
    main()
